#!/usr/bin/env python
# -*- coding:utf-8 -*-

import numpy as np

def get_list_by_class(class_label, label_list):
    node_index_list = []
    for i in range(len(label_list)):
        if label_list[i] == class_label:
            node_index_list.append(i)
    return node_index_list

def get_edge_num_by_two_class(class_a, class_b, link_mat):
    list_a = get_list_by_class(class_a)
    list_b = get_list_by_class(class_b)
    edge_num = 0
    for i in range(len(list_a)):
        for j in range(len(list_b)):
            if link_mat[list_a[i]][list_b[j]] == 1:
                edge_num += 1
    return edge_num

def get_modularity_value(label_list, link_mat):

    # TODO
    class_label_list = []
    class_num = len(class_label_list)
    graph_edge_num = np.sum(link_mat)
    for i in range(class_num):
        for j in range(class_num):
            edge_num = get_edge_num_by_two_class(class_label_list[i], class_label_list[j], link_mat)
            f = [([0] * class_num) for row in range(class_num)]
            if i == j:
                f[i][j] = edge_num / graph_edge_num
            else:
                f[i][j] = edge_num / (2 * graph_edge_num)

    f_mat = np.asarray(f)
    alpha = np.sum(f_mat, axis=1)
    modularity_value = 0
    for k in range(class_num):
        modularity_value += f_mat[k][k] - alpha ** 2

    return modularity_value

if __name__ == '__main__':
    print("starting test compute modularity value:")
